package com.gxc.string;

/**
 * 在数据加密和数据压缩中常需要对特殊的字符串进行编码。
 * 给定的字母表A由26个小写英文字母组成，即A={a，b...z}。
 * 该字母表产生的长序字符串是指定字符串中字母从左到右出现的次序与字母在字母表中出现的次序相同，且每个字符最多出现1次。
 * 例如，a，b，ab，bc，xyz等字符串是升序字符串。对字母表A产生的所有长度不超过6的升序字符串按照字典排列编码如下:a(1)，b(2)，c(3).....，z(26)，
 * ab(27)，ac(28)··..··
 * 对于任意长度不超过16的升序字符串，迅速计算出它在上述字典中的编码。
 * 输入描述:
 * 第1行是一个正整数N，表示接下来共有N行，在接下来的N行中，每行给出一个字符串。
 * 输出描述:
 * 输出N行，每行对应于一个字符串编码。
 * 示例1:
 * 输入
 * 3
 * a
 * b
 * ab
 * 输出
 * 1
 * 2
 * 27
 */
public class StringEncoding {

    public static void main(String[] args) {
        String a = "a";
        System.out.println(a.charAt(0) - 96);
        System.out.println("--------------");

        System.out.println(process("a"));
        System.out.println(process("b"));
        System.out.println(process("ab"));
    }

    public static int process(String str) {
        if (str == null || str == "") return 0;

        int length = length(str);

        int sum = 0;
        //1...length-1  的字符共有的数量
        for (int i = 1; i < length; i++) {
            sum += length(i);
        }

        char[] chars = str.toCharArray();
        //长度length，比第一个字符小的字符，共有的数量
        int pre = chars[0] - 96;
        for (int i = 1; i < pre; i++) {
            sum += base(i, length);
        }

        //长度length，第一个字符固定后，比第二个字符小的字符，共有的数量，依次递推
        for (int i = 1; i < length; i++) {
            int num = chars[i] - 96;
            for (int j = pre+1; j < num; j++) {
                sum += base(j, length-1);
            }
            pre = num;
        }

        //+1  因为 abc   循环中  int j = pre+1; j < num  会过滤  abc 本身字符，所以要加1
        return sum+1;
    }

    /**
     * 已 i 字符开头，长度 l 的字符总共有多少个
     * @param i
     * @param l
     * @return
     */
    public static int base(int i, int l) {
        if (l == 1) {
            return 1;
        }

        int sum = 0;
        for (int j = i+1; j <= 26; j++) {
            sum += base(j, l-1);
        }
        return sum;
    }

    /**
     * 长度 l 的字符总共有多少个
     * @param l
     * @return
     */
    public static int length(int l) {
        if (l ==0) return 0;

        int sum = 0;
        for (int i = 1; i <= 26; i++) {
            sum += base(i, l);
        }
        return sum;
    }



    public static int length(String str) {
        return str.length();
    }

}
